//package work.rightAnswer;
//
//class coins_322 {
//    public int coinChange(int[] coins, int amount) {
//        int[] dp = new int[amount+1];
//        dp[0] = 0;
//
//        for (int i = 1; i <= amount ; i++) {
//            int minCount = Integer.MAX_VALUE;
//            for (int j = 0; j < coins.length; j++) {
//                if(coins[j]<=i){
//                    int num = dp[i-coins[j]];
//                    if(num!=-1){
//                        minCount = Math.min(minCount,num+1);
//                    }
//                }
//            }
//            dp[i] = minCount==Integer.MAX_VALUE?-1:minCount;
//        }
//        return dp[amount];
//    }
//
//    //容量为amount时需要最少的硬币量
//    public int minCoin(int[] coins,int amount){
//        if(amount<0){
//            return -1;
//        }
//        if(amount==0){
//            return 0;
//        }
//
//        int minCount = Integer.MAX_VALUE;
//        for (int i = 0; i < coins.length; i++) {
//            int num = minCoin(coins,amount-coins[i]);
//            if(num!=-1){
//                minCount = Math.min(minCount,num+1);
//            }
//        }
//
//        return minCount==Integer.MAX_VALUE?-1:minCount;
//    }
//}